package codingforgreat.class36;

import java.security.PublicKey;

// 来自美团
// 给定两个字符串s1和s2
// 返回在s1中有多少个子串等于s2
public class Class03_MatchCount {
    public static int KmpC(String s1,String s2){
        char[] str1 = s1.toCharArray();
        char[] str2 = s2.toCharArray();
        int[] nexts = getNexts(str2);
        int i = 0;
        int j = 0;
        int count = 0;
        while(i < str1.length ){
            if(str1[i] == str2[j]){
                i++;
                j++;
                if(j == str2.length){
                    count++;
                    j = nexts[j];
                }
            }else if(nexts[j] == -1){
                i++;
            }else{
               j =  nexts[j];
            }
        }
        return count;
    }
    public static int[] getNexts(char[] str){
        if(str.length == 1){
            return new int[]{-1,0};
        }
        int[] res = new int[str.length + 1];
        res[0] = -1;
        res[1] = 0;
        int i = 2;
        int cn = 0;
        while(i < res.length){
            if(str[i - 1] == str[cn]){
                res[i++] = ++cn;
            }else if(cn != 0){
                cn = res[cn];
            }else{
                res[i++] = 0;
            }
        }
        return res;
    }

    public static void main(String[] args) {
        String s1 = "abcaaabcaaaacbabc";
        String s2 = "aa";
        System.out.println(KmpC(s1,s2));
    }
}
